﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;


//实现string类的接口，并完成测试，要求利用深拷贝和深赋值实现
//namespace Ysz
//{
//	class string
//
//	{
//
//	public:
//
//		string(const char* str = "");
//
//		string(const string& s);
//
//		string& operator=(const string& s);
//
//		~string();
//
//	private:
//
//		char* _str = nullptr;
//
//	};
//
//	string::string(const char* str)
//	{
//		char* tmp = new char[strlen(str)+1];
//		strcpy(tmp, str);
//		_str = tmp;
//	}
//	
//	string::string(const string& s)
//	{
//		//string(s._str);//这里不是调用构造函数而是创建一个匿名对象
//		string tmp(s._str);
//		swap(_str, tmp._str);
//	
//	}
//	string& string::operator=(const string& s)
//	{
//		if (this != &s)
//		{
//			string tmp(s);
//			std::swap(_str, tmp._str);
//		}
//		return *this;
//	}
//	string::~string()
//	{
//		delete[] _str;
//	}
//	
//}
//
//int main()
//{
//	Ysz::string S1 = "XXXY";
//	Ysz::string S2(S1);
//	Ysz::string S3 = "1920";
//	S1 = S3;
//	return 0;
//}


//只出现一次的数字
//https://leetcode.cn/problems/single-number/submissions/
//class Solution {
//public:
//	int singleNumber(vector<int>& nums) {
//		int val = 0;
//		for (auto num : nums)
//		{
//			val ^= num; //0异或任何数都等于原来的数，两个相同的数异或为0,a^b^b = a^0 = a;
//		}
//		return val;
//	}
//
//};

//只出现一次的数ii
//https://leetcode.cn/problems/single-number-ii/
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int a = 0, b = 0;
//        for (auto num : nums)
//        {
//            a = (a ^ num) & ~b;
//            b = (b ^ num) & ~a;
//        }
//        return a;
//        //核心思想用a和b表示三种状态，a=3b=0,a=0b=3, a=0,b=0;
//        //一个数出现3次a=0,b=0;出现一次a=3b=0,出现2次a=0b=3
//        //a = (a ^ num) & ~b;为num条件：b为0，a为0；
//        //b = (b ^ num) & ~a;为num条件：b为0，a为0；
//        // [3,3,3]
//        //1.
//        //  a = (a ^ num) & ~b = (0 ^ num) & ~0 = num & ~0 = num 
//        //  b = (b ^ num) & ~a = (0 ^ num) & ~num = num & ~num = 0 
//        //2.
//        // a = (a ^ num) & ~b = (num ^ num) & ~0 = 0 & ~0 = 0
//        // b = (b ^ num) & ~a = (0 ^ num) & ~0 = num & ~0 = num 
//        //3
//        // a = (a ^ num) & ~b = (0 ^ num) & ~num = num & ~num = 0
//        // b = (b ^ num) & ~a =  (num ^ num) & ~0 = 0 & ~0 = 0
//    }
//};


//只出现一次的数iii
//https://leetcode.cn/problems/single-number-iii/
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0;
        for (auto& num : nums)
        {
            x ^= num;
        }

        //01111111 11111111 11111111 11111111 2147483647
        //11111111 11111111 11111111 11111111 -1
        //10000000 00000000 00000000 00000000 -2147483648
        //00000000 00000000 00000000 00000000 0
        //上面两种情况异或会得到以下数据
        //10000000 00000000 00000000 00000000 -2147483648
        //如果x & -x = -2147483648 &  2147483648 //2147483648 栈溢出了
        //结果就成x & -x = -2147483648 & 0 = 00000000 00000000 00000000 00000000 = 0 拿不到第一个1的位置

        int l = x == INT_MIN ? x : x & -x;
        //这里的l是拿是x二进制从右往左第一个1的位置 也就是 那两个数第一个不相同的位置
        int n1 = 0, n2 = 0;
        for (auto& num : nums)
        {
            //用if条件把 数组分为2组
            //这2组中最重要的数据就是那两个数，其他的数会因为异或抵消为0
            //因为l是 那两个数第一个1也就是2进制第一个不同的地方，所以不用担心会分到一个组里
            if (num & l) 
            {
                n1 ^= num;
            }
            else
            {
                n2 ^= num;
            }
        }
        return { n1,n2 };
    }
};



